package com.leetcode.algorithm.y22.m07.w5;

import com.leetcode.algorithm.common.ListNode;

/**
 * 160. 相交链表
 * 
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/
 * 
 * @author jie.deng
 *
 */
public class Question0160Solution01 {
	
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// listA 中节点数目为 m
		// listB 中节点数目为 n
		// 先走m-n步，然后一起走，直到相等
		// 计算链表的长度
		int lenA = 0;
		int lenB = 0;
		ListNode curA = headA;
		while (curA != null) {
			lenA++;
			curA = curA.next;
		}
		ListNode curB = headB;
		while (curB != null) {
			lenB++;
			curB = curB.next;
		}
		// 链表长度较长者，先走N步，使剩余链表长度相等
		curA = headA;
		curB = headB;
		if (lenA > lenB) {
			int i = lenA - lenB;
			while (i > 0) {
				curA = curA.next;
				i--;
			}
		} else if (lenB > lenA) {
			int i = lenB - lenA;
			while (i > 0) {
				curB = curB.next;
				i--;
			}
		}
		// 从剩余链表中找相交的起始节点
		int i = Math.min(lenA, lenB);
		while (i > 0) {
			if (curA == curB) {
				return curA;
			}
			curA = curA.next;
			curB = curB.next;
			i--;
		}
		return null;
	}
    
}